/*
 * @lc app=leetcode id=45 lang=cpp
 *
 * [45] Jump Game II
 */
class Solution {
public:
    int jump(vector<int>& nums) {
        int len = nums.size();
        if (len < 2) {
            return 0;
        }
        int step = 0;
        int st = 0, end = 0;
        int maxgap = 0;

        while(end < len-1) {
            step++;
            maxgap = end + 1;
            for (; st <= end; st++) {
                if (nums[st] + st >= len - 1) {
                    return step;
                } else {
                    maxgap = std::max(maxgap, nums[st]+st);
                }
            }
            st = end+1;
            end = maxgap;
        }

        return step;
    }
};

